// cf-321e
// 题意：给定n(<=4000)个人排成一排，现在要将其划分成k(<=min(n, 800))组
//       （连续划分），现在已知所有人和其他人如果分到一组的不满意度，
//       求一种分组，使得最终不满意度最小。输出这个最小的不满意度。
//
// 题解：首先能够得到经典的dp，f[i][j]表示前i个人分成j组的最小不满意度。
//       转移： f[i][j] = min(f[k][j-1] + w[k+1][i]), (0<=k<i)
//       w[k+1][i]表示k+1到i这些人分成一组的不满意度和，其实就是邻接矩阵
//       k+1到i这个正方形的和除以2.
//       w函数很明显符合四边形不等式，这个转移也是经典的四边形的转移。
//
//       所以可以这样, 转移：
//         f[i][j] = min(f[k][j-1] + w[k+1][i]), (s[i-1][j]<=k<s[i][j+1])
//       s[i][j]表示f[i][j]这个状态的最优解是从s[i][j]转移过来的。
//       这个需要理论证明，但是实际可以把转移打表出来观察。
//       这样复杂度就下降了一个O(n)。
//
// run: $exec < input
#include <cstdio>
#include <algorithm>

int const  inf = 1 << 28;
int const maxn = 4007;
int const maxm = 807;
int a[maxn][maxn];
int f[maxn][maxm];
int s[maxn][maxm];
int w[maxn][maxn];
int n, m;

void scan(int & a)
{
	a = 0;
	bool flag = false;
	char ch = std::getchar();
	if (ch == '-')
		flag = true;
	else if (ch >= '0' && ch <= '9')
		a = ch - '0';

	while ((ch = std::getchar()) >= '0' && ch <= '9')
		a = a * 10 + ch - '0';
	if (flag) a = -a;
}

void init_w()
{
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++) w[i][j] = inf;

	for (int i = 1; i <= n; i++) w[i][i] = 0;
	for (int l = 2; l <= n; l++)
		for (int i = 1; i + l - 1 <= n; i++) {
			w[i][i + l - 1] = w[i][i + l - 2] + w[i + 1][i + l - 1];
			if (l > 2) w[i][i + l - 1] -= w[i + 1][i + l - 2];
			w[i][i + l - 1] += 2 * a[i][i + l - 1];
		}
}

int main()
{
	scan(n); scan(m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scan(a[i][j]);
	init_w();

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++) f[i][j] = inf;

	f[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		int ti = std::min(i, m);
		s[i][ti + 1] = i - 1;
		for (int j = ti; j >= 1; j--) {
			for (int k = s[i - 1][j]; k <= s[i][j + 1]; k++) {
			//for (int k = i - 1; k >= 0; k--) {
				int t = f[k][j - 1] + w[k + 1][i]/2;
				if (t < f[i][j]) {
					f[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
	std::printf("%d\n", f[n][m]);
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) std::cout << s[i][j] << ' ';
		std::cout << '\n';
	}
	*/
}

